package qjc.d_子串;

public class c_最小覆盖子串 {
    /**
     * 定义一个内部类 Result，用于存储最小覆盖子串的起始和结束索引，
     * 初始化目标字符串的字符计数数组，计算目标字符串中不同字符的数量，
     * 初始化源字符串的字符计数数组，初始化滑动窗口的左右指针，
     * 滑动窗口的右指针 j 遍历源字符串，获取当前右指针指向的字符，
     * 更新源字符串的字符计数， 如果当前字符的计数与目标字符串中的计数相等，增加已匹配的字符数量，
     * 当已匹配的字符数量等于目标字符串中不同字符的数量时，尝试收缩窗口，
     * 如果当前窗口的长度小于结果对象的长度，更新结果对象，获取当前左指针指向的字符，
     * 更新源字符串的字符计数，如果当前字符的计数小于目标字符串中的计数，减少已匹配的字符数量，
     * 移动左指针，直到不满足条件为止。
     */
    static class Result{
        int i;
        int j;
        public Result(int i, int j) {
            this.i = i;
            this.j = j;
        }
    }

    public String minWindow(String s, String t) {
        char[] target = t.toCharArray();
        int[] targetCount = new int[128];
        for (char c : target) {
            targetCount[c]++;
        }

        int pastTotal = 0;
        for(int count : targetCount){
            if(count > 0){
                pastTotal++;
            }
        }

        int pasted = 0;
        char[] source = s.toCharArray();
        int[] sourceCount = new int[128];
        int i = 0 , j = 0;
        Result res = null;
        while (j < source.length){
            char right = source[j];
            sourceCount[right]++;
            if(sourceCount[right] == targetCount[right]){
                pasted++;
            }
            while (i<=j && pasted == pastTotal){
                if(res == null){
                    res = new Result(i,j);
                }else {
                    if(j-i < res.j-res.i){
                        res = new Result(i,j);
                    }
                }
                char left = source[i];
                sourceCount[left]--;
                if(sourceCount[left] < targetCount[left]){
                    pasted--;
                }
                i++;
            }
            j++;
        }
        return res == null ? "" : new String(source, res.i, res.j-res.i+1);
    }
}
